#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <queue>
using namespace std;

class Solution
{

private:
    static const int mod = 1000000007;

public:
    bool threeConsecutiveOdds(vector<int> &arr)
    {
        // std::cut::
        for (int i = 0; i < arr.size() - 2; ++i)
        {
            int num1 = arr[i];
            int num2 = arr[i - 1];
            int num3 = arr[i - 2];
            if (num1 % 2 != 0 && num2 % 2 != 0 && num3 % 2 != 0)
            {
                return true;
            }
        }
        return false;
    }

    long long minSum(vector<int> &nums1, vector<int> &nums2)
    {
        long sum1 = 0, sum2 = 0;
        bool flag1 = false;
        bool flag2 = false;

        for (int i = 0; i < nums1.size(); i++)
        {
            int num = nums1[i];
            if (num == 0)
            {
                sum1++;
                flag1 = true;
            }
            else
            {
                sum1 += num;
            }
        }
        for (int i = 0; i < nums2.size(); i++)
        {
            int num = nums2[i];
            if (num == 0)
            {
                sum2++;
                flag2 = true;
            }
            else
            {
                sum2 += num;
            }
        }
        if (sum1 == sum2)
        {
            return sum1;
        }
        if (flag1 && flag2)
        {
            return min(sum1, sum2);
        }
        if (flag1 && sum2 > sum1)
        {
            return sum2;
        }
        if (flag2 && sum1 > sum2)
        {
            return sum1;
        }
        return -1;
    }

    vector<int> findEvenNumbers(vector<int> &digits)
    {
        std::set<int> ans_set;
        std::unordered_map<int, int> int_map2;
        std::map<int, int> int_map1;
        int_map2[1] = 1;
        int_map1[1] = 1;
        for (int i = 0; i < digits.size(); i++)
        {
            int a = digits[i];
            if (a != 0)
            {
                for (int j = 0; j < digits.size(); j++)
                {
                    if (i == j)
                    {
                        continue;
                    }
                    int b = digits[j];
                    for (int k = 0; k < digits.size(); k++)
                    {
                        if (k == j || k == i)
                        {
                            continue;
                        }
                        int c = digits[k];
                        if (c % 2 == 0)
                        {
                            int num = a * 100 + b * 10 + c;
                            ans_set.insert(num);
                        }
                    }
                }
            }
        }
        vector<int> ans;
        for (auto it = ans_set.begin(); it != ans_set.end(); it++)
        {
            ans.push_back(*it);
        }
        std::sort(ans.begin(), ans.end());
        return ans;
    }

    vector<string> getLongestSubsequence(vector<string> &words, vector<int> &groups)
    {
        int length = words.size();
        vector<string> ans1;
        vector<string> ans2;
        int flag1 = 1;
        int flag2 = 2;
        for (int i = 0; i < length; i++)
        {
            int group = groups[i];
            if (group == flag1)
            {
                ans1.push_back(words[i]);
                flag1 = flag1 ^ 1;
            }
            if (group == flag2)
            {
                ans2.push_back(words[i]);
                flag2 = flag2 ^ 1;
            }
        }
        if (ans1.size() > ans2.size())
        {
            return ans1;
        }
        else
        {
            return ans2;
        }
    }

    string triangleType(vector<int> &nums)
    {
        std::sort(nums.begin(), nums.end());
        if (nums[0] == nums[1] && nums[1] == nums[2])
        {
            return "equilateral";
        }
        if (nums[0] == nums[1] || nums[1] == nums[2])
        {
            return "isosceles";
        }
        if (nums[0] + nums[1] <= nums[2])
        {
            return "none";
        }
        return "scalene";
    }

    bool isZeroArray(vector<int> &nums, vector<vector<int>> &queries)
    {
        int length = nums.size();
        vector<vector<int>> dp(length);
        for (int i = 0; i < length; i++)
        {
            dp[i] = vector<int>(2, 0);
        }
        for (int i = 0; i < queries.size(); i++)
        {
            int l = queries[i][0];
            int r = queries[i][1];
            dp[l][0]++;
            dp[r][1]++;
        }
        int val = 0;
        for (int i = 0; i < length; i++)
        {
            int num = nums[i];
            vector<int> dpItem = dp[i];
            val += dpItem[0];
            if (num > val)
            {
                return false;
            }
            val -= dpItem[1];
        }
        return true;
    }

    int minZeroArray1(vector<int> &nums, vector<vector<int>> &queries)
    {
        int start = 0;
        int end = queries.size();
        int length = nums.size();
        int ans = -1;
        while (start <= end)
        {
            int mid = start + (end - start) / 2;
            vector<int> dp(length + 1, 0);
            for (int i = 0; i < mid; i++)
            {
                int l = queries[i][0];
                int r = queries[i][1];
                int val = queries[i][2];
                dp[l] += val;
                dp[r + 1] -= val;
            }
            int val = 0;
            bool flag = true;
            for (int i = 0; i < length; i++)
            {
                val += dp[i];
                if (nums[i] > val)
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                ans = mid;
                end = mid - 1;
            }
            else
            {
                start = mid + 1;
            }
        }
        return ans;
    }

    int minZeroArray(vector<int> &nums, vector<vector<int>> &queries)
    {
        int start = 0;
        int end = queries.size();
        int length = nums.size();
        vector<int> dp(length + 1, 0);
        int ans = 0;
        int val = 0;
        for (int i = 0; i < length; i++)
        {
            int num = nums[i];
            val += dp[i];
            if (num > val)
            {
                // 补充query
                while (ans < end)
                {
                    vector<int> query = queries[ans];
                    ans++;
                    int l = query[0];
                    int r = query[1];
                    int z = query[2];
                    if (r >= i)
                    {
                        val += z;
                        dp[r + 1] -= z;
                        if (num <= val)
                        {
                            break;
                        }
                    }
                }
                if (num > val)
                {
                    return -1;
                }
            }
        }
        return ans;
    }

    int maxRemoval(vector<int> &nums, vector<vector<int>> &queries)
    {
        auto cmp = [](const vector<int> &a, const vector<int> &b)
        {
            return a[0] > b[0]; // 从小到大
        };
        auto cmp1 = [](const vector<int> &a, const vector<int> &b)
        {
            return a[1] < b[1]; // 从大到小
        };
        std::priority_queue<vector<int>, std::vector<vector<int>>, decltype(cmp)> pq1(cmp);
        std::priority_queue<vector<int>, std::vector<vector<int>>, decltype(cmp1)> pq2(cmp1);

        int ans = 0;
        int numLen = nums.size();
        int queryLen = queries.size();
        std::vector<int> dp(numLen + 1, 0);
        for (int i = 0; i < queryLen; i++)
        {
            pq1.push(queries[i]);
        }
        int val = 0;
        for (int i = 0; i < numLen; i++)
        {
            int num = nums[i];
            if (val + dp[i] < num)
            {
                while (!pq1.empty() && pq1.top()[0] <= i)
                {
                    vector<int> query = pq1.top();
                    pq1.pop();
                    pq2.push(query);
                }
                while (!pq2.empty())
                {
                    vector<int> query = pq2.top();
                    pq2.pop();
                    if (query[1] < i)
                    {
                        break;
                    }
                    dp[i]++;
                    dp[query[1] + 1]--;
                    ans++;
                    if (val + dp[i] >= num)
                    {
                        break;
                    }
                }
            }
            if (val + dp[i] < num)
            {
                return -1;
            }
            val += dp[i];
        }

        return queryLen - ans;
    }

    vector<int> findWordsContaining(vector<string> &words, char x)
    {
        std::vector<int> ans;
        for (int i = 0; i < words.size(); i++)
        {
            if (words[i].find(x) != std::string::npos)
            {
                ans.push_back(i);
            }
        }
        return ans;
    }

    int longestPalindrome(vector<string> &words)
    {
        std::unordered_map<string, int> map;
        for (int i = 0; i < words.size(); i++)
        {
            map[words[i]]++;
        }
        int ans = 0;
        bool flag = false;
        for (int i = 0; i < words.size(); i++)
        {
            std::string word = words[i];
            std::string reverseWord = word;
            std::reverse(reverseWord.begin(), reverseWord.end());
            int count = map[word];
            if (word == reverseWord)
            {
                ans += count / 2 * 4;
                map[word] = count % 2;
                if (count % 2 == 1)
                {
                    flag = true;
                }
            }
            else
            {
                int count1 = map[reverseWord];
                int minCount = std::min(count, count1);
                ans += minCount * 2;
                map[word] -= minCount;
                map[reverseWord] -= minCount;
            }
        }
        return ans + (flag ? 2 : 0);
    }

    int largestPathValue(string colors, vector<vector<int>> &edges)
    {
        std::unordered_map<int, std::vector<int>> map;
        int len = colors.size();
        std::vector<int> parent(len, -1);
        for (int i = 0; i < edges.size(); i++)
        {
            vector<int> edge = edges[i];
            map[edge[0]].push_back(edge[1]);
            parent[edge[1]] = edge[0];
        }
        std::unordered_map<int, std::vector<int>> dp;
        std::vector<int> visit(len, 0);
        int ans = -1;
        for (int i = 0; i < colors.size(); i++)
        {
            if (parent[i] == -1)
            {
                std::vector<int> res = dfs(i, map, colors, dp, visit);
                if (res.size() == 0)
                {
                    return -1;
                }
                for (int i = 0; i < 26; i++)
                {
                    ans = std::max(ans, res[i]);
                }
            }
        }
        if (dp.size() < len)
        {
            return -1;
        }
        return ans;
    }

    std::vector<int> dfs(int start, std::unordered_map<int, std::vector<int>> &map,
                         string colors, std::unordered_map<int, std::vector<int>> &dp,
                         vector<int> &visit)
    {

        if (dp.find(start) != dp.end())
        {
            return dp[start];
        }
        if (visit[start] == 1)
        {
            std::vector<int> ans(0, 0);
            dp[start] = ans;
        }
        else
        {
            visit[start] = 1;
            std::vector<int> ans(26, 0);
            int color = colors[start] - 'a';
            vector<int> nexts = map[start];
            for (int i = 0; i < nexts.size(); i++)
            {
                int next = nexts[i];
                vector<int> temp = dfs(next, map, colors, dp, visit);
                if (temp.size() == 0)
                {
                    ans = temp;
                    dp[start] = ans;
                    return ans;
                }
                for (int j = 0; j < 26; j++)
                {
                    ans[j] = std::max(ans[j], temp[j]);
                }
            }
            ans[color]++;
            dp[start] = ans;
            visit[start] = 0;
        }
        return dp[start];
    }

    int differenceOfSums(int n, int m)
    {
        int num1 = 0;
        int num2 = 0;
        for (int i = 1; i <= n; i++)
        {
            if (i % m == 0)
            {
                num2 = i + num2;
            }
            else
            {
                num1 += i;
            }
        }
        return num1 - num2;
    }

    int dfs1(int start, int p, vector<vector<int>> &map,
             int maxCount)
    {
        if (maxCount < 0)
        {
            return 0;
        }
        if (maxCount == 0)
        {
            return 1;
        }
        // int key = 1000*1000*start + 1000*p + count;
        // if(cache.find(key) != cache.end())
        // {
        //     return cache[key];
        // }
        std::vector<int> &nexts = map[start];
        int ans = 1;
        for (int i = 0; i < nexts.size(); i++)
        {
            int next = nexts[i];
            if (next == p)
            {
                continue;
            }
            int dfsVal = dfs1(next, start, map, maxCount - 1);
            ans += dfsVal;
        }
        // cache[key] = ans;
        return ans;
    }

    vector<int> maxTargetNodes(vector<vector<int>> &edges1, vector<vector<int>> &edges2, int k)
    {
        int n = edges1.size() + 1;
        int m = edges2.size() + 1;
        std::vector<vector<int>> map1(n);
        std::vector<vector<int>> map2(m);
        for (auto &it : edges1)
        {
            map1[it[0]].push_back(it[1]);
            map1[it[1]].push_back(it[0]);
        }
        for (auto it : edges2)
        {
            map2[it[0]].push_back(it[1]);
            map2[it[1]].push_back(it[0]);
        }

        int maxVal = 0;
        for (int i = 0; i < m; i++)
        {
            int dfsVal = dfs1(i, -1, map2, k - 1);
            maxVal = std::max(maxVal, dfsVal);
        }
        std::vector<int> ans(n, 0);
        for (int i = 0; i < n; i++)
        {
            int dfsVal = dfs1(i, -1, map1, k);
            ans[i] = dfsVal + maxVal;
        }
        return ans;
    }

    vector<int> maxTargetNodes(vector<vector<int>> &edges1, vector<vector<int>> &edges2)
    {
        int n = edges1.size() + 1;
        int m = edges2.size() + 1;
        std::vector<vector<int>> map1(n);
        std::vector<vector<int>> map2(m);
        for (auto &it : edges1)
        {
            map1[it[0]].push_back(it[1]);
            map1[it[1]].push_back(it[0]);
        }
        for (auto &it : edges2)
        {
            map2[it[0]].push_back(it[1]);
            map2[it[1]].push_back(it[0]);
        }
        std::vector<int> dp1(n, -1);
        std::vector<int> dp2(m, -1);
        std::vector<int> flags1(2, 0);
        std::vector<int> flags2(2, 0);
        dfs2(0, -1, map1, 0, dp1, flags1);
        dfs2(0, -1, map2, 0, dp2, flags2);
        int maxVal = std::max(flags2[0], flags2[1]);
        std::vector<int> ans;
        for (int i = 0; i < n; i++)
        {
            ans.push_back(flags1[dp1[i]] + maxVal);
        }
        return ans;
    }

    void dfs2(int start, int p, vector<vector<int>> &map, int flag,
              vector<int> &dp, vector<int> &flags)
    {
        flags[flag]++;
        dp[start] = flag;
        vector<int> &nexts = map[start];
        for (int next : nexts)
        {
            if (next == p)
            {
                continue;
            }
            dfs2(next, start, map, flag ^ 1, dp, flags);
        }
    }

    int closestMeetingNode(vector<int> &edges, int node1, int node2)
    {
        std::unordered_map<int, int> map1;
        std::unordered_map<int, int> map2;
        if (node1 == node2)
            return node1;
        map1[node1] = 1;
        map2[node2] = 1;
        while (1)
        {
            node1 = node1 == -1 ? -1 : edges[node1];
            node2 = node2 == -1 ? -1 : edges[node2];
            if (node1 == node2)
            {
                return node1;
            }
            if (map1.find(node1) != map1.end() && map2.find(node2) != map2.end())
            {
                return -1;
            }
            map1[node1] = 1;
            map2[node2] = 1;
            bool a = map1.find(node2) != map1.end();
            bool b = map2.find(node1) != map2.end();
            if (a && b)
            {
                return min(a, b);
            }
            if (a)
            {
                return node2;
            }
            if (b)
            {
                return node1;
            }
        }
        return -1;
    }

    int closestMeetingNode1(vector<int> &edges, int node1, int node2)
    {
        int n = edges.size();
        auto get = [&](int x)
        {
            vector<int> d(n, -1);
            int p = x;
            int dis = 0;
            while (p != -1 && d[p] == -1)
            {
                d[p] = dis;
                p = edges[p];
                dis++;
            }
            return d;
        };
        auto d1 = get(node1);
        auto d2 = get(node2);
        int res = -1;
        for (int i = 0; i < n; i++)
        {
            if (d1[i] != -1 && d2[i] != -1 && (res == -1 || max(d1[res], d2[res]) > max(d1[i], d2[i])))
            {
                res = i;
            }
        }
        return res;
    }

    vector<vector<int>> soutArray(int m, int n)
    {
        vector<vector<int>> ans(m, vector<int>(n, 0));
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                ans[i][j] = getIndex(i, j, m, n);
                auto tmp = getIndex(ans[i][j], m, n);
                bool tmpB = tmp[0] == i && tmp[1] == j;
                std::cout << tmpB << std::endl;
            }
        }
        for (auto it = ans.begin(); it != ans.end(); ++it)
        {
            for (auto it2 = it->begin(); it2 != it->end(); ++it2)
            {
                std::cout << *it2 << " ";
            }
            std::cout << std::endl;
        }
        return ans;
    }

    int snakesAndLadders(vector<vector<int>> &board)
    {
        int m = board.size();
        int n = board[0].size();
        vector<int> visit(m * n + 2, 0);
        int ans = -1;
        int max = m * n + 1;
        auto cmp = [](const vector<int> &a, const vector<int> &b)
        {
            return a[1] > b[1];
        };
        std::priority_queue<vector<int>, std::vector<vector<int>>, decltype(cmp)> pq(cmp);
        pq.push({1, 0});
        while (!pq.empty())
        {
            vector<int> cur = pq.top();
            pq.pop();
            visit[cur[0]] = 1;
            if (cur[0] == max)
            {
                return cur[1];
            }
            for (int i = 1; i <= 6; i++)
            {
                int next = cur[0] + i;
                if (next > max)
                {
                    continue;
                }
                vector<int> dirs = getIndex(next, m, n);
                int x = dirs[0];
                int y = dirs[1];
                if (board[x][y] != -1)
                {
                    next = board[x][y];
                }
                if (visit[next] == 1)
                {
                    continue;
                }
                if (next == max)
                {
                    return cur[1] + 1;
                }
                pq.push({next, cur[1] + 1});
            }
        }
        return -1;
    }
    vector<int> getIndex(int index, int m, int n)
    {
        index--;
        int x = index / n;
        x = m - 1 - x;
        int y = index % n;
        if (m % 2 == x % 2)
        {
            y = n - 1 - y;
        }
        return {x, y};
    }

    int getIndex(int x, int y, int m, int n)
    {
        int index = (m - 1 - x) * n;
        if (m % 2 == x % 2)
        {
            y = n - 1 - y;
        }
        index += y;
        return ++index;
    }
};

int main()
{
    vector<int> nums1;
    vector<int> nums2;
    vector<int> nums3;
    nums1.push_back(1);
    nums1.push_back(2);
    nums1.push_back(2);
    nums2.push_back(2);
    nums3.push_back(1);
    Solution solution;
    long long result = solution.minSum(nums1, nums2);
    nums3.push_back(1);
    nums3.push_back(2);
    nums3.push_back(3);
    nums3.push_back(4);
    vector<int> ans = solution.findEvenNumbers(nums3);
    for (auto it = ans.begin(); it != ans.end(); ++it)
    {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 测试方法isZeroArray,传入参数nums和queries
    vector<int> nums = {1, 0, 1};
    vector<vector<int>> queries = {{0, 2}};
    bool ansIsZeroArray = solution.isZeroArray(nums, queries);
    std::cout << "ansIsZeroArray= " << ansIsZeroArray << std::endl;

    // 测试方法largestPathValue,传入参数
    // "abaca"
    // [[0,1],[0,2],[2,3],[3,4]]
    // string colors = "abaca";
    // vector<vector<int>> edges = {{0, 1}, {0, 2}, {2, 3}, {3, 4}};
    string colors = "ab";
    vector<vector<int>> edges = {{0, 1}, {1, 0}};
    int ansLargestPathValue = solution.largestPathValue(colors, edges);
    std::cout << "ansLargestPathValue= " << ansLargestPathValue << std::endl;
    int ansDifferenceOfSums = solution.differenceOfSums(5, 1); // 19
    std::cout << "ansDifferenceOfSums= " << ansDifferenceOfSums << std::endl;
    // maxTargetNodes,传入参数
    //[[0,1],[0,2],[2,3],[2,4]]
    // [[0,1],[0,2],[0,3],[2,7],[1,4],[4,5],[4,6]]
    std::vector<vector<int>> edges1 = {{0, 1}, {0, 2}, {2, 3}, {2, 4}};
    std::vector<vector<int>> edges2 = {{0, 1}, {0, 2}, {0, 3}, {2, 7}, {1, 4}, {4, 5}, {4, 6}};
    std::vector<int> ansMaxTargetNodes = solution.maxTargetNodes(edges1, edges2);

    vector<vector<int>> ansSoutArray1 = solution.soutArray(4, 5);
    vector<vector<int>> ansSoutArray2 = solution.soutArray(5, 4);
    // 测试 snakesAndLadders
    vector<vector<int>> board = {{-1, -1, -1, -1, -1, -1},
                                 {-1, -1, -1, -1, -1, -1},
                                 {-1, -1, -1, -1, -1, -1},
                                 {-1, 35, -1, -1, 13, -1},
                                 {-1, -1, -1, -1, -1, -1},
                                 {-1, 15, -1, -1, -1, -1}};
    int ansSnakesAndLadders = solution.snakesAndLadders(board);
    return 0;
}
